package com.yuqingsong.algorithm;

import java.util.Arrays;

public class Temp {
	int[] mergeSort(int[] array){
		return mergeSort(array,0,array.length-1);
	}
	int[] mergeSort(int[] array,int startIndex,int endIndex){
		if(startIndex<endIndex){
			int mid = (endIndex+startIndex)/2;
			mergeSort(array,startIndex,mid);
			mergeSort(array,mid+1,endIndex);
			merge(array, startIndex, mid, endIndex);
		}
		return array;
	}
	
	void merge(int[] array,int start,int mid,int end){
		int[] leftRight = new int[end-start+1];
		System.arraycopy(array, start, leftRight, 0, leftRight.length);
		int l=0, r= mid-start+1;
		int rStrat = r;
		int left = leftRight[l];
		int right = leftRight[r];
		for (int i = start; i <= end; i++) {
			if(left<right){
				array[i]=left;
				left =++l<rStrat?leftRight[l]:Integer.MAX_VALUE;
			}else{
				array[i]=right;
				right =++r<leftRight.length?leftRight[r]:Integer.MAX_VALUE;
			}
		}
	}
	
	public static void main(String[] args) {
		Temp t = new Temp();
		int count = 10;
//		int count = 3;
		int[] array = Sort.randomArray(count);
//		array = new int[]{7, 6, 5};
//		System.out.println(Arrays.toString(array));	
		long a = System.currentTimeMillis();
		int[] sortedArray ;
//		sortedArray = insertSort(array.clone());
		long b = System.currentTimeMillis();
//		System.out.println(Arrays.toString(sortedArray));	
		System.out.println(b-a);
		a = b;
		sortedArray = t.mergeSort(array);
		b = System.currentTimeMillis();
		System.out.println(Arrays.toString(sortedArray));	
		System.out.println(b-a);
		a = b;
		
	}
}
